package 链表;

import java.util.Stack;

public class No143重排链表 {

    /**
     *
     给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
     将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

     你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

     示例 1:

     给定链表 1->2->3->4, 重新排列为 1->4->2->3.
     示例 2:

     给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
     */

    /**
     * bobo老师的提示.取中间链表,然后后半段入栈,再用两段拼接
     * 中间链表可根据No876快慢指针法,经历一次遍历即可查找到
     */
    public static ListNode reorderList(ListNode head) {

        if(head==null||head.next==null)
            return head;

        //如果是奇数个,就返回中间偏左的
        //如果是偶数个,就返回偏左边的 (都可以接受)
        ListNode minNode = getMinNode(head);

        ListNode twoNode=minNode.next;
        minNode.next=null;//切割成两个链表

        Stack<ListNode> stack=new Stack<>();
        ListNode cur=twoNode;
        while (cur!=null){
            stack.add(cur);
            cur=cur.next;
        }

        ListNode result=new ListNode();

        cur=result;

        while (!stack.empty()&&head!=null){

            ListNode next=head.next;
            cur.next=head;
            ListNode pop = stack.pop();
            pop.next=null;
            cur.next.next=pop;
            head=next;

            cur=cur.next.next;
        }

        if(!stack.empty()) {
            ListNode pop = stack.pop();
            pop.next = null;
            cur.next = pop;
        }

        head=result.next;

        return head;
    }

    public static ListNode getMinNode(ListNode head){

        ListNode slow=head;
        ListNode fast=head.next.next;

        while (fast!=null&&fast.next!=null){

            slow=slow.next;
            fast=fast.next.next;

        }

        return slow;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,4,5,6,7,8};
        ListNode listNode = ListNode.createListNode(arr);
        ListNode result = reorderList(listNode);
        ListNode.printListNode(result);
    }

}
